package Bit;
import java.util.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.concurrent.ThreadLocalRandom;

class SevenSortTest {
    //三路快排
    public static void quickSortInternal3(int []arr,int l ,int r)
    {
        if(r-l<=15)
        {
            insertionSort(arr,l,r);
            return;
        }
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v=arr[l];
        //arr[l+1..it]<v
        int lt=1;
        int i=lt+1;
        //arr[gt..r]
        int gt=r+1;
        //i从前向后扫描和gt重合时，所有元素处理完毕
        while (i<gt)
        {
            if(arr[i]<v)
            {
                //arr[l+1.lt]<v
                //arr[lt+1,i)==v
                swap(arr,i,lt+1);
                i++;
                lt++;
            }
            else if(arr[i]>v)
            {
                swap(arr,i,gt-1);
                gt--;
            }
            else {
                i++;
            }
        }
        swap(arr,l,lt);
        quickSortInternal3(arr,l,lt-1);
        quickSortInternal3(arr,gt,r);

    }

    //二路快排
    public static void quickSort2(int[] arr) {
        quickSortInternal2(arr, 0, arr.length - 1);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        int p = paratition2(arr, l, r);
        quickSortInternal2(arr, l, p - 1);
        quickSortInternal2(arr, p + 1, r);
    }

    private static int paratition2(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        //arr[l+1...i]<=v
        //[l+1..l+1)=0
        int i = l + 1;
        //arr[j..r]>=v
        //(r...r]=0;
        int j = r;
        while (true) {//从前往后扫描，碰到第一个>=v的元素停止
            while (i <= j && arr[i] < v) {
                i++;
            }
            while (i <= j && arr[j] > v) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
        }
        return j;
    }



    //借助栈来实现快速排序
    public static void quickSortNonRecursion(int []arr)
    {
        Deque<Integer>stack=new ArrayDeque<>();
        int l=0;
        int r=arr.length-1;
        stack.push(r);
        stack.push(l);
        while(!stack.isEmpty())
        {
            int left=stack.pop();
            int right=stack.pop();
            if(left>=right)
            {
                continue;
            }
            int p=paratition(arr,left,right);
            stack.push(right);
            stack.push(p+1);
            stack.push(p-1);
            stack.push(left);
        }

    }



    //快速排序(基础版)
    private static  final ThreadLocalRandom random=ThreadLocalRandom.current();
    public static  void quickSortInternal(int []arr,int l,int r)
    {
        if(r-l<=15)
        {
            insertionSort(arr,l,r);
            return;
        }
        if(l>=r)
        {
            return ;
        }
        //先选择分区点
        //分区点左侧的所有元素都小于该元素，右侧全是大于该元素的区间
        int p=paratition(arr,l,r);
        quickSortInternal(arr,l,p-1);
        quickSortInternal(arr,p+1,r);

    }

    private static int paratition(int[] arr, int l, int r) {
        //随机选树
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v=arr[l];
        //i表示正在扫描的元素
        // [l+1...j]<v
        //[j+1...j)>=v
        int j=1;
        for(int i=l+1;i<=r;i++)
        {
            if(arr[i]<v)
            {
                swap(arr,j+1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return  j;
    }

    //核心：分区间操作，合并操作
    //语义：给我一个数组和两个索引位置，我可以把区间内的数字有序排列
    public  static void mergeSortInternal(int []arr,int l,int r)
    {//数量少的情况下，插入排序的效率更好，接近O（n）
        if(r-l<15)
        {
            insertionSort(arr);
        }
        int mid=r+((r-l)>>1);  //分成两个小区间
        mergeSortInternal(arr,l,mid);//递归排序左区间
        mergeSortInternal(arr,mid+1,r);//递归排序有区间
        //arr[mid]是左区间最大的数，arr[mid+1]是右区间最小的数
        if(arr[mid]>arr[mid+1])//两区间之间还需要排序
        {
            merge(arr,l,mid,r);
        }

    }

    private static void insertionSort(int[] arr, int l, int r) {
    for(int i=l+1;i<=r;i++)
    {
        for (int j=i;j>1&&arr[j]<arr[j-1];j--)
        {
            swap(arr,j,j-1);
        }
    }
    }
//语义：给我一个数组，我可以把[l,mid][mid+1,r]两个区间给有序排列
    public static void merge(int []arr,int l,int mid,int r)
    {
        //先创建一个新的临时数组
        int []aux=new int[r-l+1];
        for(int i=0;i<aux.length;i++)
        {
            aux[i]=arr[i+l];
        }
        int i=l;//i是左侧小数组开始的索引
        int j=mid+1;//j是右侧小数组的开始索引
      for(int k=l;k<=r;k++)
      {
          if(i>mid)
          {
              arr[k]=aux[j-l];
              j++;
          }
          else if(j>r)
          {
              arr[k]=aux[i-l];

          }
          else if(aux[i-l]<=aux[j-l])
          {
              arr[k]=aux[i-l];
              i++;
          }
          else
          {
              arr[k]=aux[j-l];
              j++;
          }
      }
    }
public  static  void shellSort(int[] arr)
        {
            int gap=arr.length>>1;
            while(gap>1)
            {
                insertionSortByGap(arr,gap);
                gap=gap>>1;
            }
            insertionSort(arr);
        }
        private  static void insertionSortByGap(int []arr,int gap)
        {
            for(int i=gap;i<arr.length;i++)
            {
                for(int j=i;j-gap>=0&&arr[j]<arr[j-gap];j-=gap)
                {
                    swap(arr,j,j-gap);
                }
            }
        }
     //堆排序
        public static  void heapSort(int []arr)
        {
            PriorityQueue<Integer> ret=new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return 0;
                }
            });
            for(int i=0;i<arr.length;i++)
            {
                ret.add(arr[i]);
            }
            System.out.println(ret);
        }
        //冒泡排序优化版
        public static void bubbleSort(int []arr)
        {
            for(int i=0;i<arr.length-1;i++) {
                boolean isSwaped = false;
                for(int j=0;j<arr.length-1-i;j++)
                {
                    if(arr[j]>arr[j+1])
                    {
                        swap(arr,j,j+1);
                        isSwaped=true;
                    }
                }
            }
        }
        //二分法优化直接插入排序
        public  static void insertionSortBS(int[]arr)
        {
            for (int i = 1; i < arr.length; i++) {
                int val = arr[i];
                int left = 0;
                int right = i;
                while (left < right) {
  //                int mid = left + ((right - left) >> 1);
                    int mid = (left + right) >> 1;
                    if (val < arr[mid]) {
                        right = mid;
                    }else {
                        // val >= arr[mid]
                        left = mid + 1;
                    }
                }
                // 搬移left..i的元素
                for (int j = i; j > left; j--) {
                    arr[j] = arr[j - 1];
                }
                // left就是val插入的位置
                arr[left] = val;
            }
        }

        //直接插入排序
        public static void insertionSort(int []arr)
        {
            //已排序区间[0,i]
            //未排序区间[i...n]
            for(int i=1;i<arr.length;i++)
            {
                for(int j=i;j>0&&arr[j]<arr[j-1];j--)
                {
                    swap(arr,j,j-1);
                }
            }
        }
        //双向选择排序
        public static void selectionSortOP(int []arr)
        {
            int low=0;
            int high=arr.length-1;
            while(low<=high)
            {
                int min=low;//找到无序区间的最小值
                int max=low;//找到无序区间的最大值
                for(int i=low+1;i<=high;i++)
                {
                    if(arr[i]<arr[min])
                    {
                        min=i;
                    }
                    if(arr[i]>arr[max])
                    {
                        max=i;
                    }
                }
                swap(arr,low,min);
                if(max==low)
                {
                    max=min;
                }
                swap(arr,max,high);
                low+=1;
                high-=1;
            }
        }
        //选择排序
      public static void selectionSort(int []arr)
      {
          //无序区间[0，i]，有序区间[]
          //流程：先从i+1开始向后遍历，找到最小的元素，然后交还arr【min】和arr【i】的位置
          //i++，扩大有序区间，继续从i+1开始往后遍历寻找【i..length】之间的最小元素.
    for(int i=0;i<arr.length-1;i++)
    {
        int min=i;
        for(int j=i+1;j< arr.length;j++)
        {
            if(arr[j]<arr[min])
            {
                min=j;
            }
        }
        swap(arr,min,i);
    }


      }
      public  static void swap(int []arr,int left,int right)
      {
          int temp=0;
          temp=arr[right];
          arr[right]=arr[left];
          arr[left]=temp;
      }

  }

